package labuladong.第三章.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Demo02 {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
    }

    public static List<Integer> findAnagrams(String s, String t) {
        int left = 0, right = 0, start = 0, match = 0;
        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> windows = new HashMap<>();
        List<Integer> res = new ArrayList<>();

        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        for(char c : tArr) {
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }

        while (right < sArr.length) {
            char c1 = sArr[right];
            if(needs.containsKey(c1)) {
                windows.put(c1, windows.getOrDefault(c1, 0) + 1);
                if(windows.get(c1) == needs.get(c1)) {
                    match++;
                }
            }

            right++;

            while (match == needs.size()) {
                if(right- left == needs.size()) {
                    res.add(left);
                }
                char c2 = sArr[left];
                if(windows.containsKey(c2)) {
                    if (windows.get(c2) == 1) {
                        windows.remove(c2);
                    }
                    if(!windows.containsKey(c2) || windows.get(c2) < needs.get(c2)) {
                        match--;
                    }
                }
                left++;
            }
        }
        return res;
    }
}
